1. Field
Embodiments of the invention relate to the field of link state routing protocols; and more specifically, to the handling of Link State Identifier collisions during link state assignment.
2. Background
Link state routing protocols such as Open Shortest Path First (OSPF) (e.g., as defined in RFC 2328, April 1998) use Link State Identifiers (LSIDs) as keys when identifying Link State Advertisements (LSAs). LSAs for different routes that share the same LSID may cause various problems including an incorrect topology view, data mapping problems, multiple routes pointing to the same LSA, etc.
For the majority of routes, the LSAs associated with each route are assigned an LSID that is equivalent to the network address of that route. The network address for a route is calculated by performing a bitwise AND operation on the route prefix and the route mask. For example, since the network address for the route [10.0.0.0, 255.255.0.0] is 10.0.0.0, LSAs for that route are typically assigned an LSID value of 10.0.0.0.
While routes with the same prefix are deemed different if their masks differ, the network address of those routes can be the same. For example, the routes [10.0.0.0, 255.255.0.0] and [10.0.0.0, 255.255.255.0] are different yet share the same network address of 10.0.0.0. Thus, the LSIDs for LSAs associated with these routes would collide. In such a case, the RFC 2328 describes an algorithm that attempts to assign different LSIDs for the LSAs for those routes (the algorithm is specified in Appendix E of RFC 2328). The LSID collision handling algorithm in RFC 2328 selects the route with the longer mask and performs a bitwise NOT operation on that mask, performs a bitwise OR operation on that result with the route prefix, and assigns the result as the LSID. For example, using the two routes above, the route [10.0.0.0, 255.255.255.0] is selected, the result of the bitwise NOT operation on the mask 255.255.255.0, which equals 0.0.0.255, is bitwise ORed with the route prefix 10.0.0.0 resulting in a value of 10.0.0.255, which is then assigned as the LSID for LSAs of that route. The route that is not selected is assigned an LSID that is equivalent to the network address.
The LSID collision handling algorithm described in RFC 2328 does not handle LSID collisions correctly when one of the colliding routes is a host route. A host route is a route with a host mask (e.g., 255.255.255.255). For example, consider the routes [10.0.0.0, 255.255.255.0] and [10.0.0.0, 255.255.255.255], which have the same network address (10.0.0.0). According to the LSID collision handling algorithm of RFC 2328, the route [10.0.0.0, 255.255.255.255] (which is a host route) is selected, the result of the bitwise NOT operation on the mask 255.255.255.255, which equals 0.0.0.0, is bitwise ORed with the route prefix 10.0.0.0 resulting in a value of 10.0.0.0, which is then assigned as the LSID for LSAs of that route. Thus, using the LSID collision handling algorithm of RFC 2328, the different routes [10.0.0.0, 255.255.255.0] and [10.0.0.0, 255.255.255.255] will have LSAs that share the same LSID of 10.0.0.0. Therefore, the LSID collision handling algorithm described in RFC 2328 as applied to host routes results in the LSAs of different routes sharing the same LSID which can result in the problems described above.